{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Absolute Difference Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询差绝对值的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个数组 <code>a</code> 的 <strong>差绝对值的最小值</strong> 定义为：<code>0 <= i < j < a.length</code> 且 <code>a[i] != a[j]</code> 的<strong> </strong><code><span style=\"\">|a[i] - a[j]|</span></code> 的 <strong>最小值</strong>。如果 <code>a</code> 中所有元素都 <strong>相同</strong> ，那么差绝对值的最小值为 <code>-1</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，数组 <code>[5,<strong>2</strong>,<strong>3</strong>,7,2]</code> 差绝对值的最小值是 <code>|2 - 3| = 1</code> 。注意答案不为 <code>0</code> ，因为 <code>a[i]</code> 和 <code>a[j]</code> 必须不相等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> 和查询数组 <code>queries</code> ，其中 <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code> 。对于每个查询 <code>i</code> ，计算 <strong>子数组</strong> <code>nums[l<sub>i</sub>...r<sub>i</sub>]</code> 中 <strong>差绝对值的最小值</strong> ，子数组 <code>nums[l<sub>i</sub>...r<sub>i</sub>]</code> 包含 <code>nums</code> 数组（下标从 <strong>0</strong> 开始）中下标在 <code>l<sub>i</sub></code> 和 <code>r<sub>i</sub></code> 之间的所有元素（包含 <code>l<sub>i</sub></code> 和 <code>r<sub>i</sub></code> 在内）。</p>\n",
    "\n",
    "<p>请你返回 <code>ans</code> <strong>数组</strong>，其中 <code>ans[i]</code> 是第 <code>i</code> 个查询的答案。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是一个数组中连续的一段元素。</p>\n",
    "\n",
    "<p><code>|x|</code> 的值定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>x >= 0</code> ，那么值为 <code>x</code> 。</li>\n",
    "\t<li>如果 <code>x < 0</code> ，那么值为 <code>-x</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]\n",
    "<b>输出：</b>[2,1,4,1]\n",
    "<b>解释：</b>查询结果如下：\n",
    "- queries[0] = [0,1]：子数组是 [<strong>1</strong>,<strong>3</strong>] ，差绝对值的最小值为 |1-3| = 2 。\n",
    "- queries[1] = [1,2]：子数组是 [<strong>3</strong>,<strong>4</strong>] ，差绝对值的最小值为 |3-4| = 1 。\n",
    "- queries[2] = [2,3]：子数组是 [<strong>4</strong>,<strong>8</strong>] ，差绝对值的最小值为 |4-8| = 4 。\n",
    "- queries[3] = [0,3]：子数组是 [1,<strong>3</strong>,<strong>4</strong>,8] ，差的绝对值的最小值为 |3-4| = 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]\n",
    "<b>输出：</b>[-1,1,1,3]\n",
    "<strong>解释：</strong>查询结果如下：\n",
    "- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。\n",
    "- queries[1] = [0,2]：子数组是 [<strong>4</strong>,<strong>5</strong>,2] ，差绝对值的最小值为 |4-5| = 1 。\n",
    "- queries[2] = [0,5]：子数组是 [<strong>4</strong>,<strong>5</strong>,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。\n",
    "- queries[3] = [3,5]：子数组是 [2,<strong>7</strong>,<strong>10</strong>] ，差绝对值的最小值为 |7-10| = 3 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 100</code></li>\n",
    "\t<li><code>1 <= queries.length <= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 <= l<sub>i</sub> < r<sub>i</sub> < nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-absolute-difference-queries](https://leetcode.cn/problems/minimum-absolute-difference-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-absolute-difference-queries](https://leetcode.cn/problems/minimum-absolute-difference-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,8]\\n[[0,1],[1,2],[2,3],[0,3]]', '[4,5,2,2,7,10]\\n[[2,3],[0,2],[0,5],[3,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        positions = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            positions[nums[i]].append(i)\n",
    "\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            prev = None\n",
    "            gap = float(\"inf\")\n",
    "            for x in range(1, 101):\n",
    "                cur_pos = positions[x]\n",
    "                pos = bisect.bisect_left(cur_pos, l)\n",
    "                if pos < len(cur_pos) and cur_pos[pos] <= r:\n",
    "                    if prev is not None:\n",
    "                        gap = min(gap, x - prev)\n",
    "                    prev = x\n",
    "            if gap == float(\"inf\"):\n",
    "                gap = -1\n",
    "            ans.append(gap)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        hashmap = defaultdict(list)\n",
    "        for i , num in enumerate(nums):\n",
    "            hashmap[num].append(i)\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        \n",
    "        for i , (l , r) in enumerate(queries):\n",
    "            p = -1\n",
    "            val = inf\n",
    "            for k in range(1,101):\n",
    "                idxs = hashmap[k]\n",
    "                cnt = bisect.bisect_right(idxs,r) - bisect.bisect_left(idxs,l)\n",
    "                if cnt == r - l + 1:\n",
    "                    break\n",
    "                if cnt > 0:\n",
    "                    if p != -1:\n",
    "                        val = min(val,k - p)\n",
    "                    p = k\n",
    "            else:\n",
    "                if val != inf:\n",
    "                    ans[i] = val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 将每个数字对应的下标存入哈希表\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i,num in enumerate(nums):\n",
    "            dic[num].append(i)\n",
    "        \n",
    "        res=[-1]*len(queries)\n",
    "        # 查询\n",
    "        for i,(l,r) in enumerate(queries):\n",
    "            pre=-inf\n",
    "            minv=inf\n",
    "            # 遍历1~100中的数字是否存在于区间[l,r]中，相邻数之差最小\n",
    "            for j in range(1,101):\n",
    "                a=bisect.bisect_left(dic[j],l)\n",
    "                b=bisect.bisect_right(dic[j],r)-1\n",
    "                if a<=b: \n",
    "                    minv=min(minv,j-pre)\n",
    "                    pre=j\n",
    "            # 区间内没有不相同的数据\n",
    "            if minv!=inf:\n",
    "                res[i]=minv\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 将每个数字对应的下标存入哈希表\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i,num in enumerate(nums):\n",
    "            dic[num].append(i)\n",
    "        \n",
    "        res=[-1]*len(queries)\n",
    "        # 查询\n",
    "        for i,(l,r) in enumerate(queries):\n",
    "            pre=-inf\n",
    "            minv=inf\n",
    "            # 遍历1~100中的数字是否存在于区间[l,r]中，相邻数之差最小\n",
    "            for j in range(1,101):\n",
    "                a=bisect.bisect_left(dic[j],l)\n",
    "                b=bisect.bisect_right(dic[j],r)-1\n",
    "                if a<=b: \n",
    "                    minv=min(minv,j-pre)\n",
    "                    pre=j\n",
    "            # 区间内没有不相同的数据\n",
    "            if minv!=inf:\n",
    "                res[i]=minv\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        b = [[] for _ in range(110)]\n",
    "        for i, x in enumerate(nums):\n",
    "            b[x].append(i)\n",
    "        res = []\n",
    "        for l, r in queries:\n",
    "            pre = -inf\n",
    "            ans = inf\n",
    "            for i in range(1, 101):\n",
    "                j = bisect_left(b[i], l)\n",
    "                if j != len(b[i]) and b[i][j] <= r:\n",
    "                    ans = min(ans, i - pre)\n",
    "                    pre = i\n",
    "            res.append(ans if ans < inf else -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        tree=[0]*n*4\n",
    "        def creattree(x,y,p):\n",
    "            if x==y:\n",
    "                ret=1<<nums[x]\n",
    "            else:\n",
    "                ret=0\n",
    "                mid=(x+y)//2\n",
    "                ret|=creattree(x,mid,p*2+1)\n",
    "                ret|=creattree(mid+1,y,p*2+2)\n",
    "            tree[p]=ret\n",
    "            return ret\n",
    "        creattree(0,n-1,0)\n",
    "        #for i in range(2*n):\n",
    "            #print(i,str(bin(tree[i])))\n",
    "        def find(x):\n",
    "            #print(str(bin(x)))\n",
    "            ret=float(\"inf\")\n",
    "            i=0\n",
    "            ls=[]\n",
    "            while x:\n",
    "                if x>>i &1:\n",
    "                    ls.append(i)\n",
    "                    x=x^(1<<i)\n",
    "                i+=1\n",
    "            #print(ls)\n",
    "            if len(ls)<=1:\n",
    "                return ret\n",
    "            for i in range(len(ls)-1):\n",
    "                if ls[i+1]-ls[i]:\n",
    "                    ret=min(ret,ls[i+1]-ls[i])\n",
    "\n",
    "            return ret\n",
    "        def query(l,r,tl,tr,p):\n",
    "            #print(l,r,tl,tr,p)\n",
    "            if l==tl and r==tr:\n",
    "                #print(\"ret=\",str(bin(tree[p])))\n",
    "                return tree[p]\n",
    "            mid=(tl+tr)//2\n",
    "            ret=0\n",
    "            if mid>=r:\n",
    "                ret=query(l,r,tl,mid,2*p+1)\n",
    "            elif mid+1<=l:\n",
    "                ret=query(l,r,mid+1,tr,2*p+2)\n",
    "            else:\n",
    "                ret=query(l,mid,tl,mid,2*p+1)|query(mid+1,r,mid+1,tr,2*p+2)\n",
    "            #print(l,r,tl,tr,p,ret)\n",
    "            #print(\"ret=\",str(bin(ret)))\n",
    "            return ret\n",
    "        ans=[]\n",
    "        for a,b in queries:\n",
    "            #print(a,b)\n",
    "            tmp=find(query(a,b,0,n-1,0))\n",
    "            if tmp==float(\"inf\"):\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n, arr):\n",
    "        self.d = [0] * (4 * n+5)\n",
    "        self.tag = [0] * (4 * n +5)\n",
    "        self.build(1, n, 1, arr) \n",
    "    def build(self, l, r, p, arr):\n",
    "        if l == r:\n",
    "            self.d[p] = 1 << (arr[l-1] - 1)\n",
    "            return \n",
    "        else:\n",
    "            mid = (l + r) >> 1\n",
    "            self.build(l, mid, 2 * p, arr) \n",
    "            self.build(mid+1, r, 2 * p + 1, arr) \n",
    "            self.d[p] = self.d[2*p] | self.d[2*p+1]\n",
    "    def putdown(self, l, r, p):\n",
    "        mid = (l + r) >> 1\n",
    "\n",
    "    def query(self, l, r, p, x, y):\n",
    "        if x <= l and r <= y:\n",
    "            return self.d[p]\n",
    "        else:\n",
    "            mid = (l + r) >> 1\n",
    "            #print(l, mid, r, p,x,y, len(self.tag))\n",
    "            if self.tag[p]:\n",
    "                self.putdown(l, r, p)\n",
    "            a1 = a2 = 0 \n",
    "            if x <= mid:\n",
    "                a1 = self.query(l, mid, p*2, x, y) \n",
    "            if y >= mid + 1:\n",
    "                #print(l, mid, r, p,x,y, len(self.tag))\n",
    "                a2 = self.query(mid+1, r, p*2+1, x, y) \n",
    "            return a1 | a2  \n",
    "    \n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums) \n",
    "        m = len(queries) \n",
    "        bt = BIT(n, nums)\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            a = bt.query(1, n, 1, l+1, r+1)\n",
    "            pre = -1\n",
    "            tmp = float('inf') \n",
    "            for i in range(100):\n",
    "                if (a >> i) & 1:\n",
    "                    if pre>=0:\n",
    "                        tmp = min(tmp, i - pre)\n",
    "                    pre = i \n",
    "            if tmp < float('inf'):\n",
    "                ans.append(tmp)\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        C = 100\n",
    "        n = len(nums)\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "        ans = []\n",
    "        for left,right in queries:\n",
    "            last = -inf\n",
    "            best = inf\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right+1][j]:\n",
    "                    best = min(best, j - last)\n",
    "                    last = j\n",
    "            if best == inf:\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "        return ans\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # dp[0] = [0] * (max(nums) + 1)\n",
    "        N, ans, dp = max(nums), [], [[0] * (max(nums) + 1)]\n",
    "        \n",
    "        for num in nums:\n",
    "            t = dp[-1][:]   # 拷贝之前的\n",
    "            t[num] += 1\n",
    "            dp.append(t)\n",
    "\n",
    "        for l, r in queries:\n",
    "            diff = [i for x, y, i in zip(dp[r + 1], dp[l], range(N + 1)) if y != x]\n",
    "            ans.append(min([b - a for a, b in zip(diff, diff[1:])] or [-1]))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        count = []\n",
    "        lst = [0] * 100\n",
    "        count.append(lst[:])\n",
    "        for num in nums:\n",
    "            lst[num - 1] += 1\n",
    "            count.append(lst[:])\n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            lst = [k for k in range(100) if count[j + 1][k] - count[i][k] > 0]\n",
    "            n = len(lst)\n",
    "            if n == 1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                add = 100\n",
    "                for ind in range(n - 1):\n",
    "                    add = add if add < lst[ind + 1] - lst[ind] else lst[ind + 1] - lst[ind]\n",
    "                ans.append(add)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        pre_sum = [[0] * (101) for _ in range(n + 1)]\n",
    "        ans = [-1] * m\n",
    "        for i, x in enumerate(nums):\n",
    "            pre_sum[i + 1][:] = pre_sum[i]\n",
    "            pre_sum[i + 1][x] += 1\n",
    "        #print(pre_sum)\n",
    "        for p, (l, r) in enumerate(queries):\n",
    "            pre = diff = inf\n",
    "            for i in range(1, 101):\n",
    "                if pre_sum[r + 1][i] - pre_sum[l][i] >= 1:\n",
    "                    #print(l, r, i)\n",
    "                    if pre != inf:\n",
    "                        diff = min(diff, i - pre)\n",
    "                    pre = i\n",
    "            if diff != inf:\n",
    "                ans[p] = diff\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        presum = [[0] * 101 for _ in range(len(nums) + 1)]\n",
    "\n",
    "        for i in range(1, len(presum)):\n",
    "            for j in range(1, 101):\n",
    "                if j == nums[i - 1]:\n",
    "                    presum[i][j] = presum[i - 1][j] + 1\n",
    "                else:\n",
    "                    presum[i][j] = presum[i - 1][j]\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        for ii, (l, r) in enumerate(queries):       \n",
    "            rr = presum[r + 1]\n",
    "            ll = presum[l]\n",
    "            pre = None\n",
    "            dd = float('inf')\n",
    "            for i in range(1, 101):\n",
    "                if rr[i] - ll[i] > 0:\n",
    "                    if pre is not None:\n",
    "                        dd = min(dd, i - pre)\n",
    "                    \n",
    "                    pre = i\n",
    "\n",
    "            if dd != float('inf'):\n",
    "                ans[ii] = dd\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        presum = [[0] * 101 for _ in range(len(nums) + 1)]\n",
    "\n",
    "        for i in range(1, len(presum)):\n",
    "            for j in range(1, 101):\n",
    "                if j == nums[i - 1]:\n",
    "                    presum[i][j] = presum[i - 1][j] + 1\n",
    "                else:\n",
    "                    presum[i][j] = presum[i - 1][j]\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        for ii, (l, r) in enumerate(queries):       \n",
    "            rr = presum[r + 1]\n",
    "            ll = presum[l]\n",
    "            pre = None\n",
    "            dd = float('inf')\n",
    "            for i in range(1, 101):\n",
    "                if rr[i] - ll[i] > 0:\n",
    "                    if pre is not None:\n",
    "                        dd = min(dd, i - pre)\n",
    "                    \n",
    "                    pre = i\n",
    "\n",
    "            if dd != float('inf'):\n",
    "                ans[ii] = dd\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = [[0] * 101 for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(101):\n",
    "                cnt[i + 1][j] = cnt[i][j]\n",
    "            cnt[i + 1][nums[i]] += 1\n",
    "        ret = [0] * len(queries)\n",
    "        for i, (l, r) in enumerate(queries):\n",
    "            c = [cnt[r + 1][j] - cnt[l][j] for j in range(101)]\n",
    "            last = -1\n",
    "            k = 200\n",
    "            # print(l,r, [j for j in range(101) if c[j]])\n",
    "            for j in range(101):\n",
    "                if not c[j]:\n",
    "                    continue\n",
    "                if last != -1:\n",
    "                    k = min(k, j - last)\n",
    "                last = j\n",
    "            ret[i] = k if k != 200 else -1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 元素 c 的最大值\n",
    "        C = 100\n",
    "\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            # last 记录上一个出现的元素\n",
    "            # best 记录相邻两个元素差值的最小值\n",
    "            last = 0\n",
    "            best = float(\"inf\")\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right + 1][j]:\n",
    "                    if last != 0:\n",
    "                        best = min(best, j - last)\n",
    "                    last = j\n",
    "\n",
    "            if best == float(\"inf\"):\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        dp=[[0]*101 for _ in range(n+1)]\n",
    "        # 前缀和记录每个数在区间内出现的次数\n",
    "        for i in range(n):\n",
    "            for j in range(1,101):\n",
    "                dp[i+1][j]=dp[i][j]\n",
    "                dp[i+1][nums[i]]+=1\n",
    "        \n",
    "        res=[-1]*len(queries)\n",
    "        # 顺序查询\n",
    "        for i,(l,r) in enumerate(queries):\n",
    "            minv=inf\n",
    "            pre=-inf\n",
    "            # 判断区间内是否有不同数字出现\n",
    "            for j in range(1,101):\n",
    "                if dp[r+1][j]-dp[l][j]>0:\n",
    "                    minv=min(minv,j-pre)\n",
    "                    pre=j\n",
    "            # 区间内存在不同的数字 \n",
    "            if minv!=inf:\n",
    "                res[i]=minv\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        c = 100\n",
    "        pre = [[0] * c for _ in range(len(nums))]\n",
    "        pre[0][nums[0]-1] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            n = nums[i]\n",
    "            for j in range(c):\n",
    "                pre[i][j] = pre[i-1][j]\n",
    "            pre[i][n-1] += 1\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            l, r = q\n",
    "            last_n = None\n",
    "            min_abs_diff = 101\n",
    "            for j in range(c):\n",
    "                cnt_r = pre[r][j]\n",
    "                cnt_l = pre[l-1][j] if l > 0 else 0\n",
    "                if cnt_r - cnt_l > 0:\n",
    "                    if last_n:\n",
    "                        min_abs_diff = min(min_abs_diff, j + 1 - last_n)\n",
    "                    last_n = j + 1\n",
    "            if min_abs_diff == 101:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(min_abs_diff)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [[0 for _ in range(101)]]\n",
    "        for i in nums:\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][i]+=1\n",
    "\n",
    "        res = []\n",
    "        for l, r in queries:\n",
    "            best = inf\n",
    "            last = 0\n",
    "            for i in range(1, 101):\n",
    "                if pre[r+1][i]-pre[l][i]:\n",
    "                    if last:\n",
    "                        best = min(best, i-last)\n",
    "                    last = i\n",
    "            res.append(best if best!=inf else -1)\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "#         C = 100\n",
    "\n",
    "#         n = len(nums)\n",
    "#         pre = [[0] * (C + 1)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             pre.append(pre[-1][:])\n",
    "#             pre[-1][num] += 1\n",
    "\n",
    "#         ans = list()\n",
    "#         for left, right in queries:\n",
    "#             last = 0\n",
    "#             best = float(\"inf\")\n",
    "#             for j in range(1, C + 1):\n",
    "#                 if pre[left][j] != pre[right + 1][j]:\n",
    "#                     if last != 0:\n",
    "#                         best = min(best, j - last)\n",
    "#                     last = j\n",
    "            \n",
    "#             if best == float(\"inf\"):\n",
    "#                 best = -1\n",
    "#             ans.append(best)\n",
    "        \n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 元素 c 的最大值\n",
    "        C = 100\n",
    "\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            # last 记录上一个出现的元素\n",
    "            # best 记录相邻两个元素差值的最小值\n",
    "            last = 0\n",
    "            best = float(\"inf\")\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right + 1][j]:\n",
    "                    if last != 0:\n",
    "                        best = min(best, j - last)\n",
    "                    last = j\n",
    "            \n",
    "            if best == float(\"inf\"):\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        \n",
    "        # 计算前缀和数组，用于快速统计子数组中每个数字出现的次数。\n",
    "        max_num = max(nums)\n",
    "        prefix_count = [[0] * (max_num + 1) for _ in range(len(nums) + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(max_num + 1):\n",
    "                prefix_count[i+1][j] = prefix_count[i][j]\n",
    "            prefix_count[i+1][num] += 1\n",
    "        \n",
    "        for l, r in queries:\n",
    "            # 使用前缀和数组统计子数组中每个数字出现的次数。\n",
    "            counts = [prefix_count[r+1][i] - prefix_count[l][i] for i in range(max_num + 1)]\n",
    "            \n",
    "            min_diff = float('inf')\n",
    "            prev = -1\n",
    "            \n",
    "            for i, count in enumerate(counts):\n",
    "                if count > 0:\n",
    "                    if prev != -1:\n",
    "                        min_diff = min(min_diff, i - prev)\n",
    "                    prev = i\n",
    "            \n",
    "            ans.append(min_diff if min_diff != float('inf') else -1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "#         n = len(nums)\n",
    "#         pre = [[0 for _ in range(101)] for _ in range(n+1)]\n",
    "#         for i in range(n):\n",
    "#             for j in range(1, 101):\n",
    "#                 pre[i+1][j] = pre[i][j] + (1 if nums[i]==j else 0)\n",
    "\n",
    "#         res = []\n",
    "#         for l, r in queries:\n",
    "#             best = inf\n",
    "#             last = 0\n",
    "#             for i in range(1, 101):\n",
    "#                 if pre[r+1][i]-pre[l][i]:\n",
    "#                     print(i)\n",
    "#                     if last:\n",
    "#                         best = min(best, i-last)\n",
    "#                     last = i\n",
    "#             res.append(best if best!=inf else -1)\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        C = 100\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            last = 0\n",
    "            best = float(\"inf\")\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right + 1][j]:\n",
    "                    if last != 0:\n",
    "                        best = min(best, j - last)\n",
    "                    last = j\n",
    "            \n",
    "            if best == float(\"inf\"):\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 元素 c 的最大值\n",
    "        C = 100\n",
    "\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            # last 记录上一个出现的元素\n",
    "            # best 记录相邻两个元素差值的最小值\n",
    "            last = 0\n",
    "            best = float(\"inf\")\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right + 1][j]:\n",
    "                    if last != 0:\n",
    "                        best = min(best, j - last)\n",
    "                    last = j\n",
    "            \n",
    "            if best == float(\"inf\"):\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 元素 c 的最大值\n",
    "        C = 100\n",
    "\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        pre = [[0] * (C + 1)]\n",
    "        for i, num in enumerate(nums):\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][num] += 1\n",
    "\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            # last 记录上一个出现的元素\n",
    "            # best 记录相邻两个元素差值的最小值\n",
    "            last = 0\n",
    "            best = float(\"inf\")\n",
    "            for j in range(1, C + 1):\n",
    "                if pre[left][j] != pre[right + 1][j]:\n",
    "                    if last != 0:\n",
    "                        best = min(best, j - last)\n",
    "                    last = j\n",
    "            \n",
    "            if best == float(\"inf\"):\n",
    "                best = -1\n",
    "            ans.append(best)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        cnt = [0] * 101\n",
    "        cnts = [cnt]\n",
    "        for num in nums:\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][num] += 1\n",
    "\n",
    "        ans = [100] * len(queries)\n",
    "        for j, (l, r) in enumerate(queries):\n",
    "            prev = 0\n",
    "            for i in range(1,101):\n",
    "                diff = cnts[r+1][i] - cnts[l][i]\n",
    "                if diff == r - l +1:\n",
    "                    ans[j] = -1\n",
    "                    break \n",
    "                elif diff:\n",
    "                    if prev:\n",
    "                        ans[j] = min(ans[j], i-prev)\n",
    "                    prev = i\n",
    "            if ans[j] == 100:\n",
    "                ans[j] = -1\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [[0 for _ in range(101)]]\n",
    "        for i in nums:\n",
    "            pre.append(pre[-1][:])\n",
    "            pre[-1][i]+=1\n",
    "\n",
    "        res = []\n",
    "        for l, r in queries:\n",
    "            best = inf\n",
    "            last = 0\n",
    "            for i in range(1, 101):\n",
    "                if pre[r+1][i]-pre[l][i]:\n",
    "                    print(i)\n",
    "                    if last:\n",
    "                        best = min(best, i-last)\n",
    "                    last = i\n",
    "            res.append(best if best!=inf else -1)\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "#         C = 100\n",
    "\n",
    "#         n = len(nums)\n",
    "#         pre = [[0] * (C + 1)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             pre.append(pre[-1][:])\n",
    "#             pre[-1][num] += 1\n",
    "\n",
    "#         ans = list()\n",
    "#         for left, right in queries:\n",
    "#             last = 0\n",
    "#             best = float(\"inf\")\n",
    "#             for j in range(1, C + 1):\n",
    "#                 if pre[left][j] != pre[right + 1][j]:\n",
    "#                     if last != 0:\n",
    "#                         best = min(best, j - last)\n",
    "#                     last = j\n",
    "            \n",
    "#             if best == float(\"inf\"):\n",
    "#                 best = -1\n",
    "#             ans.append(best)\n",
    "        \n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        mn,mx = min(nums), max(nums)\n",
    "        cnt = [0] * (mx-mn+1)\n",
    "        cnts = [cnt]\n",
    "        for num in nums:\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][num-mn] += 1\n",
    "\n",
    "        ans = [100] * len(queries)\n",
    "        for j, (l, r) in enumerate(queries):\n",
    "            prev = 0\n",
    "            for i in range(mn,mx+1):\n",
    "                diff = cnts[r+1][i-mn] - cnts[l][i-mn]\n",
    "                if diff == r - l +1:\n",
    "                    ans[j] = -1\n",
    "                    break \n",
    "                elif diff:\n",
    "                    if prev:\n",
    "                        ans[j] = min(ans[j], i-prev)\n",
    "                    prev = i\n",
    "            if ans[j] == 100:\n",
    "                ans[j] = -1\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        mn,mx = min(nums), max(nums)\n",
    "        cnt = [0] * (mx-mn+1)\n",
    "        cnts = [cnt]\n",
    "        for num in nums:\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][num-mn] += 1\n",
    "\n",
    "        ans = [100] * len(queries)\n",
    "        for j, (l, r) in enumerate(queries):\n",
    "            prev = 0\n",
    "            for i in range(mn,mx+1):\n",
    "                diff = cnts[r+1][i-mn] - cnts[l][i-mn]\n",
    "                if diff == r - l +1:\n",
    "                    break \n",
    "                elif diff:\n",
    "                    if prev:\n",
    "                        ans[j] = min(ans[j], i-prev)\n",
    "                    prev = i\n",
    "            if ans[j] == 100:\n",
    "                ans[j] = -1\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        mn,mx = min(nums), max(nums)\n",
    "        cnt = [0] * (mx-mn+1)\n",
    "        cnts = [cnt]\n",
    "        for num in nums:\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][num-mn] += 1\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        for j, (l, r) in enumerate(queries):\n",
    "            diffs = [i for i in range(mx-mn+1) if cnts[r+1][i] > cnts[l][i]]\n",
    "            if len(diffs) > 1:\n",
    "                ans[j] = min(b-a for a,b in pairwise(diffs))\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #前缀和（4524 ms，218.7 MB）\n",
    "        s = [Counter()]\n",
    "        for i in nums :\n",
    "            s.append(s[-1].copy())\n",
    "            s[-1][i] += 1\n",
    "        res = []\n",
    "        for l, r in queries :\n",
    "            t = s[r+1] - s[l]\n",
    "            keys = list(t.keys())\n",
    "            if len(keys) == 1 :\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                keys.sort()\n",
    "                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #前缀和（4524 ms，218.7 MB）\n",
    "        s = [Counter()]\n",
    "        for i in nums :\n",
    "            s.append(s[-1].copy())\n",
    "            s[-1][i] += 1\n",
    "\n",
    "        res = []\n",
    "        for l, r in queries :\n",
    "            t = s[r+1] - s[l]\n",
    "            keys = list(t.keys())\n",
    "            if len(keys) == 1 :\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                keys.sort()\n",
    "                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        s = [Counter()]\n",
    "        for i in nums :\n",
    "            s.append(s[-1].copy())\n",
    "            s[-1][i] += 1\n",
    "        res = []\n",
    "        for l, r in queries :\n",
    "            t = s[r+1] - s[l]\n",
    "            keys = list(t.keys())\n",
    "            if len(keys) == 1 :\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                keys.sort()\n",
    "                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = [Counter()]\n",
    "        for i in nums :\n",
    "            s.append(s[-1].copy())\n",
    "            s[-1][i] += 1\n",
    "        res = []\n",
    "        for l, r in queries :\n",
    "            t = s[r+1] - s[l]\n",
    "            keys = list(t.keys())\n",
    "            if len(keys) == 1 :\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                keys.sort()\n",
    "                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        m = max(nums)\n",
    "        dp = []\n",
    "        for x in range(1, m+1):\n",
    "            lst = [int(x==num) for num in nums]\n",
    "            dp.append(list(accumulate(lst, initial=0)))\n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            pre = -inf\n",
    "            cur = inf\n",
    "            for x in range(1, m+1):\n",
    "                if dp[x-1][j+1] - dp[x-1][i]:\n",
    "                    if x-pre < cur:\n",
    "                        cur = x-pre\n",
    "                    pre = x\n",
    "            ans.append(cur if cur < inf else -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ps = {}\n",
    "        s = sorted(set(nums))\n",
    "        for x in s:\n",
    "            ps[x] = list(accumulate([num == x for num in nums], initial=0))\n",
    "        \n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            t = []\n",
    "            for x in s:\n",
    "                if ps[x][r + 1] - ps[x][l] > 0:\n",
    "                    t.append(x)\n",
    "            if len(t) == 1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(min(y - x for x, y in pairwise(t)))\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
